package com.test.demo.algorithm.sort;

public class InsertingSort {

    /**
     * 插入排序
     * 假定前i个数是有序的，第i个数插入前i个数
     * 4s
     */
    public static int[] insertingSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    /**
     * 插入排序
     * 假定前i个数是有序的，第i个数插入前i个数
     * 3s
     */
    public static int[] insertingSort2(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //优化，增加一个变量，如果没有交换了，已经找到位置了就退出一层循环
            boolean flag = true;
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    flag = false;
                }
                if (flag) {
                    break;
                }
            }
        }
        return array;
    }

    /**
     * 把待插入的数拿出来，从待插入的前一个比较，如果比待插入的数大，则往后挪一位，直到找到合适的位置，直接插入结束遍历。
     * 691ms
     *
     * @param array
     * @return
     */
    public static int[] insertingSort3(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //待插入的数
            int insertvalue = array[i];
            int insertindex = i;
            //从待插入的前一个数开始遍历，如果大于插入的数就往后移
            while (insertindex > 0 && array[insertindex - 1] > insertvalue) {
                array[insertindex] = array[insertindex - 1];
                insertindex--;
            }
            //找到插入的位置
            array[insertindex] = insertvalue;
        }
        return array;
    }

    /**
     * 可以通过二分法插入
     * @param array
     * @return
     */
    public static int[] insertingSort4(int[] array) throws Exception {
        throw new Exception("异常了");
        //return array;
    }
}